#include "./dynamic-search.h"

void createSortTree(BinTree &tree, NodeDateType *nodes, int size)
{
	createTree(tree, nodes[0]);
	for (int i = 1; i < size; i++)
	{
		insertSortTree(tree, nodes[i]);
	}
}

void insertSortTree(BinTree &tree, NodeDateType e)
{
	// 插入之前，先根据这个元素索引到父节点
	BinTree p = searchSortTree(tree, tree, e);
	if (p->data == e)
	{
		// 树中已有相同结点，不再插入
		return;
	}
	// 初始化新结点
	BTNode *node = new BTNode;
	node->data = e;
	node->lchild = node->rchild = nullptr;
	// 判断索引到的父节点的大小，小则作为左孩子，大则作为右孩子
	// 空树则直接作为根结点
	if (p == nullptr)
	{
		tree = node;
	}
	else if (e < p->data)
	{
		p->lchild = node;
	}
	else
	{
		p->rchild = node;
	}
}

BTNode *searchSortTree(BinTree &tree, BinTree &parent, NodeDateType e)
{
	// 查找到底了就返回这个结点的父结点
	if (tree == nullptr)
	{
		return parent;
	}
	// 若当前值和查找值相同则返回当前结点
	if (tree->data == e)
	{
		return tree;
	}
	// 否则比较大小，小则在左子树递归查找，大则右子树递归查找
	if (e < tree->data)
	{
		return searchSortTree(tree->lchild, tree, e);
	}
	else
	{
		return searchSortTree(tree->rchild, tree, e);
	}
}